package com.techgig.codecontest.problem.monkeysinthegarden;

import java.util.Arrays;

public class CandidateCode {
	private static class Tree implements Comparable<Tree> {
		int h, i;
		public Tree(int h, int i) {
			this.h = h;
			this.i = i;
		}
		@Override
		public int compareTo(Tree t) {
			return t.h - h;
		}
	}
    public static int monkey(int[] input1)
    {
    	Tree[] t = new Tree[input1.length];
    	for(int i = 0; i < input1.length; i++)
    		t[i] = new Tree(input1[i], i);
    	Arrays.sort(t);
    	int mt = 0, md = t.length / 2;
    	for(int ti = 0; ti < t.length && 2 * t[ti].h + md > mt; ti++) {
    		for(int tj = ti + 1; tj < t.length && t[ti].h + t[tj].h + md > mt; tj++) {
    			int d = Math.abs(t[ti].i - t[tj].i);
    			if(d > md)
    				d = t.length - d;
    			int time = t[ti].h + t[tj].h + d;
    			if(time > mt)
    				mt = time;
    		}
    	}
    	return mt;
    }
	public static void main(String[] args) {
		int[] h = {1, 2, 3, 4};
		System.out.println(monkey(h));
	}
}
